package hot_100;

import java.util.Arrays;

public class 跳跃游戏II {
    public static void main(String[] args) {

    }

    public int jump(int[] nums) {
        int n = nums.length;
        int ans = 0;
        int maxleng = 0;
        int end = 0;
        for (int i = 0; i < n; i++) {
            maxleng = Math.max(maxleng, i + nums[i]);
            if (i == end) {
                end = maxleng;
                ans++;
            }
        }
        return ans;
    }

//    public int jump(int[] nums) {
//        int n = nums.length;
//        int[] cnt = new int[n + 1];
//        Arrays.fill(cnt, Integer.MAX_VALUE >> 1);
//        cnt[0] = 0;
//        for (int i = 0; i < n; i++) {
//            int m = nums[i];
//            for (int j = i; j <= Math.min(n - 1, i + m); j++) {
//                cnt[j] = Math.min(cnt[j], cnt[i] + 1);
//            }
//        }
//        return cnt[n-1];
//    }
}
